package io.tec.cloud.algorithm.c01_v20220601;

/**
 * 局部最小值问题：
 * <p>
 * 1个数，如果左边存在数字，并且小于它左边的数，
 * 如果右边存在数字，并且小于它右边的数，
 * 这个数字就是这个数组的一个最小值
 * <p>
 * <p>
 * 局部最小值
 * 题目：给定一个无序数组，并且相邻两个元素不相等，求局部最小值
 * 解题思路
 * <p>
 * 存在3种情况：
 * <p>
 * 最左边两个值，如果0位置处的值小于1位置处，则0位置处为局部最小
 * 最右边的两个值，如果N-1位置处的值小于N-2位置处的值，则N-1处的值为局部最小值
 * 当0位置处的值大于1位置处的值，N-1的值大于N-2处的值，则中间某个位置或者某几个位置必然会有局部最小值
 */
public class BSAwesome {

    public static int getGlobalMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        if (arr.length == 1) {
            return 0;
        }

        if (arr[0] < arr[1]) {
            return 0;
        }

        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        int L = 1;
        int R = arr.length - 1;
        int mid;
        while (L < R) {
            mid = L + ((R - L) >> 1);

            /*if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else*/
            if (arr[mid] > arr[mid - 1]) {
                R = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                L = mid + 1;
            } else {
                return mid;
            }
        }
        // 因为一定存在最小值，所以最后这个数一定是最小值：L==mid==R
        return L;
//        return R;
    }

    public static int getMinIndex2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        if (arr.length == 1) {
            return 0;
        }

        if (arr[0] < arr[1]) {
            return 0;
        }

        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        int L = 1;
        int R = arr.length - 1;
        int mid;
        while (L <= R) {
            mid = L + ((R - L) >> 1);

            /*if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else*/
            if (arr[mid] > arr[mid - 1]) {
                R = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                L = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static boolean test(int[] arr, int minIndex) {
        if (arr == null || arr.length == 0) {
            return true;
        }

        if (arr.length == 1) {
            return true;
        }

        if (minIndex == 0) {
            return arr[0] < arr[1];
        }

        if (minIndex == arr.length - 1) {
            return arr[arr.length - 1] < arr[arr.length - 2];
        }

//        SortTestUtil.p(arr);
        return arr[minIndex] < arr[minIndex - 1] && arr[minIndex] < arr[minIndex + 1];
    }

    // 课上的代码
    public static int getLessIndex1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }


    public static void main(String[] args) {
        int testTimes = 5000000;
        int maxValue = 500;
        int maxLength = 50;
        for (int i = 0; i < testTimes; i++) {
//            int[] original = {};
            int[] original = generatorArray(maxValue, maxLength);
//            int[] original = {0, -317, -300};
//            int[] original = {2,1,2,3,4,5,6,7,8,9,10};
//            int[] original = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2};
            final int globalMinIndex1 = getMinIndex2(original);
            final int globalMinIndex2 = getGlobalMinIndex(original);
//            final int globalMinIndex = getGlobalMinIndex(original);
//            SortTestUtil.p(original);
//            System.out.println(globalMinIndex);
            if (!test(original, globalMinIndex1) || !test(original, globalMinIndex2)) {
                System.out.println("error");
                return;
            }
        }

        System.out.println("finish");
    }
    /*{
        int[] arr = {3,2,9,2,1,4,0,10,9,0,8,3,5,6,7,1,9,2,4,0,7};
        System.out.println(getGlobalMinIndex(arr));
        System.out.println(getLessIndex(arr));
    }*/

    private static int[] generatorArray(int maxValue, int maxLength) {

        int[] arr = new int[(int) (Math.random() * maxLength + 1)];
        arr[0] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue);
        for (int i = 1; i < arr.length; i++) {
            do {
                arr[i] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue);
            } while (arr[i] == arr[i - 1]);
        }
        return arr;
    }

    /**
     * 知乎上的暴力
     *
     * @param arr
     * @return
     */
    public static int getLessIndex(int[] arr) {
        if (arr.length == 0) {
            return -1;
        }
        if (arr.length == 1) {
            return 0;
        }
        if (arr.length > 1 && arr[0] < arr[1]) {
            return 0;
        }
        if (arr.length > 1 && arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                return i;
            }
        }

        return -1;
    }
}
